#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution
{

private:
    unordered_map<int, int> m; // key ： 整数n， value ： 和为 n 的完全平方数的最少数量
public:
    int numSquares(int n)
    {
        // 先初始化用的到的平方数
        int t = 4;
        int i = 3;
        while (t <= n)
        {
            m[t] = 1;
            t = i * i;
            i++;
        }

        // 写状态转移方程，画图，识图

        for (size_t i = 0; i < n; i++)
        {
            for (size_t j = 4; j < i; j++)
            {
                if (m[j] != 0)
                {
                    int k = i - j;
                    if (m[k] != 0)
                    {
                        if (m[i] == 0)
                        {
                            m[i] = 1000000;
                        }
                        if (m[j] + m[k] < m[i])
                        {
                            m[i] = m[j] + m[k];
                        }
                    }
                }
            }
        }
        for (size_t i = 0; i < n; i++)
        {
            std::cout << m[i] << std::endl;
        }

        return m[n];
    }
};
int main(int argc, char **argv)
{
    Solution s;
    s.numSquares(999);
    return 0;
}
